目標：
這題主要目的在於再進一步引導讀者去思考如何做出一個適合dp的鏈結關係。

原題：

Question:
Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:
   1         3       3         2       1
    \        /      /         / \       \
     3     2       1         1   3       2
    /     /         \                     \
   2     1           2                     3

分析/解題：
還記得什麼是二元搜尋樹嗎？
不知道的話，可以翻閱前面的Day 17的介紹歐！
簡言之，一個合法的BST除了左邊的節點要全小於根節點，
右邊的節點要全大於根節點外，其左右子樹也要是BST才行。
觀察n=3的狀況，我們可以將其歸納成3類：
以1為根節點/以2為根節點/以3為根節點。

首先是1為根節點的狀況：
左邊沒有比其小的節點，故只有一種可能；
右邊有2跟3的組合，相當於n=2的時候的狀況(2種)。
(2跟3等價於1跟2兩個節點會有的組合)

再來是2為根節點的狀況：
左邊只有1種可能(1這個節點)；
右邊也只有1種可能(3這個節點)。

最後是3為根節點的狀況：
左邊是1跟2的組合(2種)，
右邊只有1種可能。

如果我們將n的組合命名為函式f(n)，
那麼顯然f(0)=1(只有一種可能)，f(1)=1。

計算n=3的組合算法為：
f(0) * f(2) + f(1) * f(1) + f(2) * f(0)

掌握這個規律的狀態，我們可以得到f(n)的計算方式：
f(0) * f(n-1) + f(1) * f(n-2) + … + f(n-1) * f(0)
那麼，從f(1)開始起算的話，
我們可以一路疊加將f(1)到f(n-1)都算出來，
最後得到我們要的f(n)。
讓f(n)能夠化成f(n-1)或較小的項次的組合，一路化簡到能直接確認的值，
所以這個就是典型的動態規劃的範例。

Java:

class Solution {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < i; ++j) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
}

Python:

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        
        for i in range(1, n + 1):
            for j in range(0, i):
                dp[i] += dp[j] * dp[i - j - 1]
            
        return dp[n]

面試實際可能會遇到的問題：
「時間/空間複雜度？」
(O(n²), O(n)
由於計算時兩層迴圈最大都要經歷n，故時間上會和n的平方相關)

「可以改成遞迴的方式嗎？」
(可以，我們只要將dp改成字典或HashMap，開一個函式search，
令其在找不到值的時候呼叫自己如 sum += search(i-1) * search(n-i)，
最後也會如同迴圈的解法一樣一路拆解到最底下，
讀者可以自行嘗試看看，實測上兩者速度在實作正確的狀況下，
應該是感受不出太明顯的差異的。)

此外，本文的解其實等同於Catalan number，讀者可參考閱讀。

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0189. Rotate Array (Easy)